home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 August: Tool Chest / Dev.CD Aug 94.toast / New System Software Extensions / OpenDoc A6 / OpenDoc Parts Framework / OPF / Found / BCCollec / Structs / Trees / BCTree.cpp next >
Encoding:
Text File  |  1994-04-21  |  7.4 KB  |  292 lines  |  [TEXT/MPS ]
  1. //  The C++ Booch Components (Version 2.1)
  2. //  (C) Copyright 1990-1993 Grady Booch. All Rights Reserved.
  3. //
  4. //  Restricted Rights Legend
  5. //  Use, duplication, or disclosure is subject to restrictions as list forth 
  6. //  in subdivision (c)(1)(ii) of the Rights in Technical Data and Computer 
  7. //  Software clause at DFARS 252.227-7013. 
  8. //
  9. //  BCBTree.cpp
  10. //
  11. //  This file contains the definitions for the binary tree.
  12.  
  13. #include "BCExcept.h"
  14. #include "BCTree.h"
  15.  
  16. template<class Item, class StorageManager>
  17. BC_TBinaryTree<Item, StorageManager>::BC_TBinaryTree()
  18.   : fRep(0) {}
  19.  
  20. template<class Item, class StorageManager>
  21. BC_TBinaryTree<Item, StorageManager>::
  22.   BC_TBinaryTree(const BC_TBinaryTree<Item, StorageManager>& t)
  23.     : fRep(t.fRep)
  24. {
  25.   if (fRep)
  26.     fRep->fCount++;
  27. }
  28.  
  29. template<class Item, class StorageManager>
  30. BC_TBinaryTree<Item, StorageManager>::~BC_TBinaryTree()
  31. {
  32.   Clear();
  33. }
  34.  
  35. template<class Item, class StorageManager>
  36. BC_TBinaryTree<Item, StorageManager>& BC_TBinaryTree<Item, StorageManager>::
  37.   operator=(const BC_TBinaryTree<Item, StorageManager>& t)
  38. {
  39.   if (this == &t)
  40.     return *this;
  41.   Clear();
  42.   fRep = t.fRep;
  43.   if (fRep)
  44.     fRep->fCount++;
  45.   return *this;
  46. }
  47.  
  48. template<class Item, class StorageManager>
  49. BC_Boolean BC_TBinaryTree<Item, StorageManager>::
  50.   operator==(const BC_TBinaryTree<Item, StorageManager>& t) const
  51. {
  52.   return (fRep == t.fRep);
  53. }
  54.  
  55. template<class Item, class StorageManager>
  56. BC_Boolean BC_TBinaryTree<Item, StorageManager>::
  57.   operator!=(const BC_TBinaryTree<Item, StorageManager>& t) const
  58. {
  59.   return !operator==(t);
  60. }
  61.  
  62. template<class Item, class StorageManager>
  63. void BC_TBinaryTree<Item, StorageManager>::Clear()
  64. {
  65.   Purge(fRep);
  66.   fRep = 0;
  67. }
  68.  
  69. template<class Item, class StorageManager>
  70. void BC_TBinaryTree<Item, StorageManager>::Insert(const Item& i, BC_Child child)
  71. {
  72.   BC_Assert((!fRep || (fRep->fParent == 0)),
  73.     BC_XNotRoot("BC_TBinaryTree::Insert", BC_kNotRoot));
  74.   if (child == BC_kLeft)
  75.     fRep = new BC_TBinaryNode<Item, StorageManager>(i, 0, fRep, 0);
  76.   else
  77.     fRep = new BC_TBinaryNode<Item, StorageManager>(i, 0, 0, fRep);
  78. }
  79.  
  80. template<class Item, class StorageManager>
  81. void BC_TBinaryTree<Item, StorageManager>::
  82.   Append(const Item& i, BC_Child child, BC_Child after)
  83. {
  84.   if (!fRep)
  85.     fRep = new BC_TBinaryNode<Item, StorageManager>(i, 0, 0, 0);
  86.   else {
  87.     if (after == BC_kLeft) {
  88.       if (child == BC_kLeft)
  89.         fRep->fLeft =
  90.           new BC_TBinaryNode<Item, StorageManager>(i, fRep, fRep->fLeft, 0);
  91.       else
  92.         fRep->fLeft =
  93.           new BC_TBinaryNode<Item, StorageManager>(i, fRep, 0, fRep->fLeft);
  94.     } else {
  95.       if (child == BC_kLeft)
  96.         fRep->fRight =
  97.           new BC_TBinaryNode<Item, StorageManager>(i, fRep, fRep->fRight, 0);
  98.       else
  99.         fRep->fRight =
  100.           new BC_TBinaryNode<Item, StorageManager>(i, fRep, 0, fRep->fRight);
  101.     }
  102.   }      
  103. }
  104.  
  105. template<class Item, class StorageManager>
  106. void BC_TBinaryTree<Item, StorageManager>::Remove(BC_Child child)
  107. {
  108.   BC_Assert((fRep != 0), BC_XIsNull("BC_TBinaryTree::Remove", BC_kNull));
  109.   if (child == BC_kLeft) {
  110.     Purge(fRep->fLeft);
  111.     fRep->fLeft = 0;
  112.   } else {
  113.     Purge(fRep->fRight);
  114.     fRep->fRight = 0;
  115.   }
  116. }
  117.  
  118. template<class Item, class StorageManager>
  119. void BC_TBinaryTree<Item, StorageManager>::
  120.   Share(BC_TBinaryTree<Item, StorageManager>& t, BC_Child child)
  121. {
  122.   BC_TBinaryNode<Item, StorageManager>* ptr = t.fRep;
  123.   BC_Assert((ptr != 0), BC_XIsNull("BC_TBinaryTree::Share", BC_kNull));
  124.   if (child == BC_kLeft)
  125.     ptr = t.fRep->fLeft;
  126.   else
  127.     ptr = t.fRep->fRight;
  128.   Clear();
  129.   fRep = ptr;
  130.   fRep->fCount++;
  131. }
  132.  
  133. template<class Item, class StorageManager>
  134. void BC_TBinaryTree<Item, StorageManager>::
  135.   SwapChild(BC_TBinaryTree<Item, StorageManager>& t, BC_Child child)
  136. {
  137.   BC_Assert((fRep != 0), BC_XIsNull("BC_TBinaryTree::SwapChild", BC_kNull));
  138.   BC_Assert((!t.fRep || (t.fRep->fParent == 0)),
  139.     BC_XNotRoot("BC_TBinaryTree::SwapChild", BC_kNotRoot));
  140.   BC_TBinaryNode<Item, StorageManager>* curr;
  141.   if (child == BC_kLeft) {
  142.     curr = fRep->fLeft;
  143.     fRep->fLeft = t.fRep;
  144.   } else {
  145.     curr = fRep->fRight;
  146.     fRep->fRight = t.fRep;
  147.   }
  148.   if (t.fRep)
  149.     t.fRep->fParent = fRep;
  150.   t.fRep = curr;
  151.   if (t.fRep)
  152.     t.fRep->fParent = 0;
  153. }
  154.  
  155. template<class Item, class StorageManager>
  156. void BC_TBinaryTree<Item, StorageManager>::Child(BC_Child child)
  157. {
  158.   if (child == BC_kLeft)
  159.     LeftChild();
  160.   else
  161.     RightChild();
  162. }
  163.  
  164. template<class Item, class StorageManager>
  165. void BC_TBinaryTree<Item, StorageManager>::LeftChild()
  166. {
  167.   BC_Assert((fRep != 0), BC_XIsNull("BC_TBinaryTree::LeftChild", BC_kNull));
  168.   BC_TBinaryNode<Item, StorageManager>* curr = fRep;
  169.   fRep = fRep->fLeft;
  170.   if (curr->fCount > 1) {
  171.     curr->fCount--;
  172.     if (fRep)
  173.       fRep->fCount++;
  174.   }  else {
  175.     if (fRep)
  176.       fRep->fParent = 0;
  177.     if (curr->fRight)
  178.       curr->fRight->fParent = 0;
  179.     delete curr;
  180.   }
  181. }
  182.  
  183. template<class Item, class StorageManager>
  184. void BC_TBinaryTree<Item, StorageManager>::RightChild()
  185. {
  186.   BC_Assert((fRep != 0), BC_XIsNull("BC_TBinaryTree::RightChild", BC_kNull));
  187.   BC_TBinaryNode<Item, StorageManager>* curr = fRep;
  188.   fRep = fRep->fRight;
  189.   if (curr->fCount > 1) {
  190.     curr->fCount--;
  191.     if (fRep)
  192.       fRep->fCount++;
  193.   } else {
  194.     if (fRep)
  195.       fRep->fParent = 0;
  196.     if (curr->fLeft)
  197.       curr->fLeft->fParent = 0;
  198.     delete curr;
  199.   }
  200. }
  201.  
  202. template<class Item, class StorageManager>
  203. void BC_TBinaryTree<Item, StorageManager>::Parent()
  204. {
  205.   BC_Assert((fRep != 0), BC_XIsNull("BC_TBinaryTree::Parent", BC_kNull));
  206.   if (!fRep->fParent)
  207.     Clear();
  208.   else {
  209.     fRep->fCount--;
  210.     fRep = fRep->fParent;
  211.     if (fRep)
  212.       fRep->fCount++;
  213.   }
  214. }
  215.  
  216. template<class Item, class StorageManager>
  217. void BC_TBinaryTree<Item, StorageManager>::SetItem(const Item& i)
  218. {
  219.   BC_Assert((fRep != 0), BC_XIsNull("BC_TBinaryTree::SetItem", BC_kNull));
  220.   fRep->fItem = i;
  221. }
  222.  
  223. template<class Item, class StorageManager>
  224. BC_Boolean BC_TBinaryTree<Item, StorageManager>::HasChildren() const
  225. {
  226.   return (!fRep || fRep->fLeft || fRep->fRight);
  227. }
  228.  
  229. template<class Item, class StorageManager>
  230. BC_Boolean BC_TBinaryTree<Item, StorageManager>::IsNull() const
  231. {
  232.   return (fRep == 0);
  233. }
  234.  
  235. template<class Item, class StorageManager>
  236. BC_Boolean BC_TBinaryTree<Item, StorageManager>::IsShared() const
  237. {
  238.   return (fRep) ? (fRep->fCount > 1) : 0;
  239. }
  240.  
  241. template<class Item, class StorageManager>
  242. BC_Boolean BC_TBinaryTree<Item, StorageManager>::IsRoot() const
  243. {
  244.   return (!fRep || (fRep->fParent == 0));
  245. }
  246.  
  247. template<class Item, class StorageManager>
  248. const Item& BC_TBinaryTree<Item, StorageManager>::ItemAt() const
  249. {
  250.   BC_Assert((fRep != 0), BC_XIsNull("BC_TBinaryTree::ItemAt", BC_kNull));
  251.   return fRep->fItem;
  252. }
  253.  
  254. template<class Item, class StorageManager>
  255. Item& BC_TBinaryTree<Item, StorageManager>::ItemAt()
  256. {
  257.   BC_Assert((fRep != 0), BC_XIsNull("BC_TBinaryTree::ItemAt", BC_kNull));
  258.   return fRep->fItem;
  259. }
  260.  
  261. template<class Item, class StorageManager>
  262. void* BC_TBinaryTree<Item, StorageManager>::operator new(size_t s)
  263. {
  264.   return StorageManager::Allocate(s);
  265. }
  266.  
  267. template<class Item, class StorageManager>
  268. void BC_TBinaryTree<Item, StorageManager>::operator delete(void* p, size_t s)
  269. {
  270.   StorageManager::Deallocate(p, s);
  271. }
  272.  
  273. template<class Item, class StorageManager>
  274. void BC_TBinaryTree<Item, StorageManager>::
  275.   Purge(BC_TBinaryNode<Item, StorageManager>*& curr)
  276. {
  277.   if (curr) {
  278.     if (curr->fCount > 1)
  279.       curr->fCount--;
  280.     else {
  281.       Purge(curr->fLeft);
  282.       if (curr->fLeft)
  283.         curr->fLeft->fParent = 0;
  284.       Purge(curr->fRight);
  285.       if (curr->fRight)
  286.         curr->fRight->fParent = 0;
  287.       delete curr;
  288.       curr = 0;
  289.     }
  290.   }
  291. }
  292.